﻿#pragma once
#include "Index.h"

class IAdvantageShuffle
{
public:
	/**
	 * 优势洗牌.
	 * https://leetcode.cn/problems/advantage-shuffle
	 * 贪心 数组 双指针 排序
	 *
	 * 给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
	 * 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
	 *
	 * 1 <= nums1.length <= 10^%
	 * nums2.length == nums1.length
	 * 0 <= nums1[i], nums2[i] <= 10^9
	 */
	virtual std::vector<int> advantageCount(std::vector<int>& nums1, std::vector<int>& nums2) = 0;
};

class AdvantageShuffle
{
public:
	class Solution:public IAdvantageShuffle
	{
	public:
		std::vector<int> advantageCount(std::vector<int>& nums1, std::vector<int>& nums2) override
		{
			if (nums1.empty() || nums2.empty() || nums1.size() != nums2.size())
				return {};
			const int numsSize = nums1.size();

			std::vector<int> usedForward(numsSize, 0);
			for (int i = 0; i < numsSize; ++i)
				usedForward[i] = i;

			std::sort(nums1.begin(), nums1.end());

			std::vector<int> ans(numsSize, -1);
			for(int i=0;i<numsSize;++i)
			{
				int index = greaterLowerBound(nums1, nums2[i]);

				while ((index >= 0 && index < numsSize) && usedForward[index] != index)
					index = usedForward[index];

				if (index < 0 || index>=numsSize)
					continue;
		
				ans[i] = nums1[index];

				int forward = index + 1;
				while (forward < numsSize && usedForward[forward] != forward)
					forward = usedForward[forward];
				usedForward[index] = forward;
			}

			std::vector<int> leftNums;
			for(int i=0;i<numsSize;++i)
			{
				if (usedForward[i] == i)
					leftNums.emplace_back(nums1[i]);
			}

			int nextLeft = 0;
			for(int i=0;i<numsSize;++i)
			{
				if (ans[i] < 0)
					ans[i] = leftNums[nextLeft++];
			}

			return ans;
		}
	private:
		//在有序数组nums中找到第一个大于target的数的索引位置，找不到返回-1
		int greaterLowerBound(std::vector<int>& nums,int target)
		{
			int ans = -1;
			if (nums.empty())
				return ans;

			int left = 0, right = nums.size() - 1;
			while(left<=right)
			{
				const int mid = left + ((right - left) >> 1);
				if (nums[mid] > target)
				{
					ans = mid;
					right = mid - 1;
				}
				else
					left = mid + 1;
			}
			return ans;
		}
	};
};

#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(AdvantageShuffleTest, advantageCount)
{
	TEST_SOLUTION1(IAdvantageShuffle,AdvantageShuffle::Solution,&)
	{
		__slnTestor.setTestTimes(10000);
		constexpr int expectAdvantage = 5000;
		constexpr int noiseSize = 1000;

		std::vector<int> nums1, nums2;
		{
			nums1 = TestingUtil::randRangeInts(expectAdvantage, 11, 50);
			nums2.resize(nums1.size(), 0);
			for (int i = 0; i < nums1.size(); ++i)
				nums2[i] = nums1[i] - 1;

			for (int i = 0; i < noiseSize; ++i)
			{
				nums1.push_back(TestingUtil::randIntBetween(0, 10));
				nums2.push_back(TestingUtil::randIntBetween(51, 100));
			}
			//打乱2个数组
			std::random_device rd;
			std::mt19937 g(rd());
			std::shuffle(nums1.begin(), nums1.end(), g);
			std::shuffle(nums2.begin(), nums2.end(), g);
		}

		auto result= solution->advantageCount(nums1, nums2);
		ASSERT_EQ(result.size(), nums2.size());

		int advantage = 0;
		for(int i=0;i<nums2.size();++i)
		{
			if (result[i] > nums2[i])
				advantage++;
		}
		ASSERT_EQ(advantage, expectAdvantage)
			<< "nums1=" << FormatedUtil::dumpFormated(result) << std::endl
			<< "nums2=" << FormatedUtil::dumpFormated(nums2) << std::endl;
	};
}
#endif